package com.cuz.hot100;

import com.cuz.hot100.datastruck.ListNode;

public class Q86partition {

    public static void main(String[] args) {
        ListNode head = ListNode.creatBy(1, 4, 3, 2, 5, 5);
        partition1(head,4).print();
    }
    public static ListNode partition1(ListNode head, int x) {
        ListNode lessNode = new ListNode();
        ListNode lessPre = lessNode;
        ListNode moreNode = new ListNode();
        ListNode morePre = moreNode;
        while (head != null) {
            ListNode[] info = removeHeadReturnNewHead(head);
            head = info[1];
            ListNode curNode = info[0];
            if (curNode.val < x) {
                lessPre.next = curNode;
                lessPre = lessPre.next;
            } else {
                morePre.next = curNode;
                morePre = morePre.next;
            }
        }
        lessPre.next = moreNode.next;
        return lessNode.next;
    }

    private static ListNode[] removeHeadReturnNewHead(ListNode node) {
        ListNode newHead = node.next;
        node.next = null;
        return new ListNode[]{node, newHead};
    }
}
